/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-08-06
 * Time:15:58
 */
//创建节点
class ListNode {
    public int data;//data用来存储数据
    public ListNode next;//用来存储下一个节点的地址
    //构造方法，用来初始化节点数据
    public ListNode(int data) {
        this.data = data;
    }
}

public class myLinkList {
    public ListNode head;//用来存储头结点

    //打印链表
    public void showList() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.data + " -> ");
            cur = cur.next;
        }
        System.out.println("null");
    }

    //头插
    public void addfrist(int data) {
        ListNode newListNode = new ListNode(data);
        // 当为空链表时，新节点就是头结点
        if(this.head == null) {
            this.head = newListNode;
        } else {
            newListNode.next = this.head;
            this.head = newListNode;
        }
    }

    // 尾插
    public void addLast(int data) {
        ListNode newListNode = new ListNode(data);
        //找最后一个节点
        if(this.head == null) {
            this.head = newListNode;
            return;
        }
        ListNode cur = this.head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = newListNode;
    }

    // 求链表的长度
    public int sizeList() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public ListNode searchPrev(int index) {
        int count = 0;
        ListNode cur = this.head;
        while (count < index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        //判断坐标是否合法
        if (index < 0 || index > sizeList()) {
            System.out.println("输入坐标不合法");
            return;
        }
        //如果在0下标下插入
        if (index == 0) {
            addfrist(data);
            return;
        }
        ListNode newListNode = new ListNode(data);
        ListNode prev = searchPrev(index);
        newListNode.next = prev.next;
        prev.next = newListNode;
    }

    public ListNode searchPrevKey(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if(cur.next.data == key) {
                return cur;
            }
            cur =cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //判断是否为null链表
        if (this.head == null) {
            System.out.println("链表为空");
            return;
        }

        //判段头结点是否为key值
        if (this.head.data == key) {
            this.head =this.head.next;
            return;
        }

        ListNode prev = searchPrevKey(key);
        if(prev!= null) {
            prev.next = prev.next.next;
        } else {
            System.out.println("没有该数字");
        }
    }

    //删除所有值为key的节点
//    public void removeAllKey(int key) {
//        ListNode prev = this.head;
//        ListNode cur = this.head.next;
//
//        while (cur != null) {
//            if(cur.data == key) {
//                prev.next = cur.next;
//                cur = cur.next;
//            } else {
//                prev = prev.next;
//                cur = cur.next;
//            }
//        }
//
//        // 判断第一个节点是否为key
//        if (this.head.data == key) {
//            this.head = this.head.next;
//        }
//    }
    public void removeAllKey(int key) {
        if(this.head == null) {
            return;
        }

        ListNode prev = this.head;
        ListNode cur = this.head.next;

        while (cur != null) {
            if(cur.data == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = prev.next;
                cur = cur.next;
            }
        }
            //处理第一值为key
        if(this.head.data == key) {
            this.head = this.head.next;
        }
    }

    // 反转一个单链表
    public void reservalList() {
        if (this.head == null || this.head.next == null) {
            return;
        }
        ListNode newhead = null;
        ListNode cur = this.head;
        while (cur!= null) {
            ListNode next = cur.next;
            cur.next = newhead;
            newhead = cur;
            cur = next;
        }

        this.head = newhead;
    }
    //清空链表
    public void clear(){
        while(this.head != null) {
            ListNode next = this.head.next;
            this.head = null;
            this.head = next;
        }
    }
//    public ListNode partition(int x){
//        ListNode bs = null;
//        ListNode be = null;
//        ListNode as = null;
//        ListNode ae = null;
//        ListNode cur = this.head;
//
//        while (cur!= null){
//
//            if(cur.data >= x){
//                if(as == null) {
//                    as = cur;
//                    ae = cur;
//                }else {
//                    ae.next = cur;
//                    ae = ae.next;
//                }
//            }else {
//                if(bs == null){
//                    bs = cur;
//                    be = cur;
//                }else {
//                    be.next = cur;
//                    be = be.next;
//                }
//
//            }
//            cur = cur.next;
//        }
//
//        if(bs == null) {
//            return as;
//        }else {
//            be.next = as;
//            if(as != null){
//                ae.next = null;
//            }
//            return bs;
//        }
//
//    }
//    public ListNode partition(int x) {
//        ListNode cur = this.head;
//        ListNode bs = null;
//        ListNode be = null;
//        ListNode as = null;
//        ListNode ae = null;
//        while (cur != null) {
//            if (cur.data < x) {
//                if (bs == null) {
//                    bs = cur;
//                    be = cur;
//                } else {
//                    be.next = cur;
//                    be = be.next;
//                }
//            }else {
//                if(as == null){
//                    as = cur;
//                    ae = cur;
//                }
//                else{
//                    ae.next = cur;
//                    ae = ae.next;
//                }
//            }
//            cur = cur.next;
//        }
//        if(bs == null)
//        {
//            return as;
//        }
//
//            be.next = as;
//          if(as != null){
//              ae.next = null;
//        }
//        return bs;
//    }
//    public ListNode deleteDuplication(ListNode pHead) {
//        ListNode newHead = new ListNode(-1);
//        ListNode tmp = newHead;
//        ListNode cur = this.head;
//        while(cur.next != null) {
//            //判断是不是只有一个节点或者是尾巴结点
//            if(cur.next != null && cur.data == cur.next.data)
//            {
//                cur = cur.next;
//            }
//            cur = cur.next;
//        }
//    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null) {
            return null;
        }
        if (headB == null){
            return null;
        }

        int lenA = 0;
        int lenB = 0;

        //pl:代表常的链表长度 ps:代表段的链表长度
        ListNode pl = headA;
        ListNode ps = headB;
        while(pl!=null){
            lenA++;
            pl = pl.next;
        }

        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        /*
        lenA 和 lenB的结果
        lenA > lenB
        lenA = lenB
        lenA < lenB
         */
        int len = lenA - lenB;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB -lenA;
        }
        //结果pl永远指向的长的链表 ps永远是指向短的链表 len永远是一个整数
        while(len!= 0){
            pl = pl.next;
            len--;
        }
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == null){
            return  null;
        }
        return pl;
    }
//    public boolean chkPalindrome() {
//        ListNode head = this.head;
//        if(head == null){
//            return true;
//        }
//        if(head.next == null){
//            return true;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        //找中间位置
//        while(fast != null && fast.next != null){
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        //反转链表
//        ListNode cur = slow.next;
//        while(cur != null){
//            ListNode curNext = cur.next;
//            cur.next = slow;
//            slow = cur;
//            cur = curNext;
//        }
//
//        //反转完毕
//        while(slow != head){
//            if(slow.data != head.data){
//                return false;
//            }
//            if(head.next == slow){
//                return true;
//            }
//            head = head.next;
//            slow = slow.next;
//        }
//        return true;
//
//        // write code here
//    }

    /**
`     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
     2X + 2C  - 2Y  = X + NC + C - Y
     X = (N - 1 )C + Y;
     */
   public ListNode detectCycle(){
       //先找出相遇的哪一点
       ListNode fast = this.head;
       ListNode slow = this.head;
       while(fast != null && fast.next != null) {
           fast = fast.next.next;
           slow = slow.next;
           if(slow == fast){
               break;
           }
       }

       if(fast == null || fast.next == null){
           return null;
       }
       //若有环，将fast拉回头结点,然后一步一步的走，当相遇的时候就是入环点
       fast = this.head;
       while(fast!= slow){
           fast = fast.next;
           slow = slow.next;
       }
       return fast;
   }


    /**
     * 给定一个链表，判断链表中是否有环
     * 若快慢指针相遇就说明有环
     */
    public boolean hasCycle(){
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    /**
     *对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
     *
     * 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
     */
    public boolean chkPalindrome(){
        //1.先找到链表的中点
        ListNode fast = this.head;
        ListNode slow = this.head;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //此时slow已经走到了中点

        //将后半链表逆置

        ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //此时后半段逆置完成，从两端开始比较是否相等

        fast = this.head;
        while(fast != slow || fast.next != slow){
            if(fast.data != slow.data){
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }

        return true;
    }

    /*
    删除链表重复节点
     */

    public ListNode deleteDuplication() {
        ListNode newhead = new ListNode(-1);
        ListNode tmp = newhead;
        ListNode cur = this.head;
        while (cur != null) {
            if (cur != null && cur.data == cur.next.data) {
                while (cur != null && cur.data == cur.next.data) {
                    cur = cur.next;
                }
                cur = cur.next;
            } else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }


        }
        //解决最后一个数字重复问题
        tmp.next = null;
        return this.head.next;
    }
    public ListNode partition(int x){
       ListNode bs = null;
       ListNode be = null;
       ListNode as = null;
       ListNode ae = null;
       ListNode cur = this.head;

       while (cur != null){
           if(cur.data < x){
               if(bs == null){
                   bs = cur;
                   be = cur;
               }else {
                   be.next = cur;
                   be = be.next;
               }
           }else {
               if (as == null){
                   as = cur;
                   ae = cur;
               }else {
                   ae.next = cur;
                   ae = ae.next;
               }
           }
           cur = cur.next;
       }
        if(bs == null){
            return as;
        }else {
            be.next = as;
            if (as!= null){
                ae.next = null;
            }
            return bs;
        }
    }
}
